#ifndef COLAHEAPIMP_CPP
#define COLAHEAPIMP_CPP
#include "ColaHeapImp.h"

template <class T>
ColaHeapImp<T>::ColaHeapImp(int largo,Puntero<FuncionHash<T>> fh,Puntero<FuncionIguales<T>> fi){
	maximo = largo;
	tope = 0;
	heap = new NodoHeap<T>*[largo];
	for(int i=0;i<largo;i++) heap[i] = NULL;
	deltaPrioridad=0;
	lista=new ListaImp<T>();
	this->hash =new Hash<T,int>(fh,fi,largo);

}

template <class T>
ColaHeapImp<T>::~ColaHeapImp(){
	vaciar();
	//this->lista=NULL;
}
		
template <class T>
void ColaHeapImp<T>::vaciar(){
	
	this->hash->vacio();
	for( int i=0;i<this->maximo;i++)
	{
		//heap[i]=NULL;
		delete heap[i];
	}
	tope=0;
}		

template <class T>
bool ColaHeapImp<T>:: encolarConPrioridad(T elemento, int puntaje){//prioridad
	if(!hash->estaDefinido(elemento)){
	if(tope+1 < maximo){
			tope++;
			//If hash estaDefinido
			if(heap[1] == NULL) {
				//Si el array esta vacio inserto
				heap[1]=new NodoHeap<T>(elemento,puntaje);
				heap[1]->posicion=1;//lo pongo en la pos 1
				hash->operator [](elemento)=1;
				return true;
			}
			else{	
				int i;
				i = this->tope;
				//asigno el tope a i para saber hasta donde tengo que recorrer
				
				/*------------------------------------------------------------------------------------------------------------------------/
				#Tengo que hacer un metodo que si esta el recurso me devuelva la posicion donde esta y llame al cambiar puntaje recurso para
				#cumplir con el punto 3 del obligatorio hablar del tema de ordenes con el Santi porque es orden 1 promedio
				------------------------------------------------------------------------------------------------------------------------/*/
				while(i>1 && heap[i/2]->prioridad < puntaje){
					//comparo por puntaje para saber donde tengo que meter el recurso
					heap[i]=heap[i/2];
					heap[i]->posicion=i;
					hash->operator [](heap[i]->dato)=i;
					i = i/2;
				}
				//inserto el recurso en la posicion correspondiente del heap	
				heap[i]=new NodoHeap<T>(elemento,puntaje);
				heap[i]->posicion=i;
				hash->operator [](elemento)=i;
				
				return true;
			}
		}
		else return false;
	}else{
//Mirar bien Preguntar lo de la suma de puntaje o el cambio de puntaje
			int pos=hash->operator [](elemento);
			hash->eliminar(elemento);
			heap[pos]->dato=elemento;
			heap[pos]->prioridad=puntaje;
			//reorganizar(pos);
			hash->operator [](elemento)=reorganizar(pos);
			return true;
			
	


	}
}
template <class T>
void ColaHeapImp<T>:: eliminar(T &dato)
{

	int pos=hash->operator [](dato);
		NodoHeap<T>* aux = heap[tope];
		tope--;
		dato = heap[pos]->dato;
		heap[pos]=aux;
		hash->eliminar(dato);
		heap[pos]->posicion=pos;
		hash->operator [](heap[pos]->dato)=heap[pos]->posicion;
			int hijo=pos;
			//Filtrado ascendente ordenando el heap por prioridad que en nuestro caso es el puntaje
			for(int i=pos; 2*i <= tope ; i=hijo){
				hijo = 2*i;
				if(hijo+1<=tope && heap[hijo+1]->prioridad > heap[hijo]->prioridad) hijo++;
				//Si fija en la posicion i y i+1 cual es mayor y lo corre a la posicion de i que es el padre
				if(heap[hijo]->prioridad > heap[i]->prioridad){
					aux = heap[i];
					heap[i] = heap[hijo];
					heap[hijo]=aux;
					//Corre el padre a la posicion del hijo
					heap[i]->posicion = i;
					heap[hijo]->posicion=hijo;
					//Actualizo la posicion heap
					hash->operator [](heap[i]->dato)=i;
					hash->operator [](heap[hijo]->dato)=hijo;
					//Actualizo la posicion en el hash

						
				}
			}
}
template <class T>
bool ColaHeapImp<T>:: desencolar(T &dato)
{
	if(tope>=1){
		//me fijo si tengo elementos en el heap
		NodoHeap<T>* aux = heap[tope];
		tope--;
		//decremento el tope
		dato = heap[1]->dato;
		delete heap[1];
		//Elimino del hash el primero
		heap[1]=aux;
		hash->eliminar(dato);
		heap[1]->posicion=1;
		hash->operator [](heap[1]->dato)=heap[1]->posicion;
		//El elemento que estaba en el tope actualizo la posicion en el hash
		//pongo en la primera posicion el elemento elemento que quedo en el tope
		int hijo=1;
		//Filtrado ascendente ordenando el heap por prioridad que en nuestro caso es el puntaje
		for(int i=1; 2*i <= tope ; i=hijo){
			hijo = 2*i;
			if(hijo+1<=tope && heap[hijo+1]->prioridad > heap[hijo]->prioridad) hijo++;
			//Si fija en la posicion i y i+1 cual es mayor y lo corre a la posicion de i que es el padre
				if(heap[hijo]->prioridad > heap[i]->prioridad){
					aux = heap[i];
					heap[i] = heap[hijo];
					heap[hijo]=aux;
					//Corre el padre a la posicion del hijo
					heap[i]->posicion = i;
					heap[hijo]->posicion=hijo;
					//Actualizo la posicion heap
					hash->operator [](heap[i]->dato)=i;
					hash->operator [](heap[hijo]->dato)=hijo;
					//Actualizo la posicion en el hash
				}			
			
		}
		return true;
	}
	else {
		return false;
	}
}
template <class T>
bool ColaHeapImp<T>::proximo(T &dato){
	if(tope>=1){
		//retorno true si hay algo en el heap y cargo la variable con el primer elemento del heap
		dato = heap[1]->dato;
		return true;
	}
	else return false;
}

template <class T>
bool ColaHeapImp<T>::esVacia(){
	return tope == 0;
}

template <class T>
bool ColaHeapImp<T>::esLlena(){
	return tope==maximo;
}

template <class T>
void ColaHeapImp<T>::setPrioridadBase(int puntaje){//prioridad
	deltaPrioridad = puntaje;
}
template <class T>
int ColaHeapImp<T>::getPrioridadBase(){
	return deltaPrioridad;
}

template<class T>
int ColaHeapImp<T>::reorganizar(int posicion){
    int hijo = 2*posicion;
	//Se fija cual es el mayor de los hijos conrespecto al padre
	if(hijo+1<=tope && heap[hijo+1]->prioridad > heap[hijo]->prioridad) hijo++;
	int padre=0;
	if(posicion/2 >=1) padre = posicion/2;
	if(hijo>0 && hijo<= tope && heap[posicion]->prioridad<heap[hijo]->prioridad){
		    	NodoHeap<T>*	aux = heap[posicion];
				heap[posicion] = heap[hijo];
				heap[hijo]=aux;
				heap[posicion]->posicion = posicion;
				heap[hijo]->posicion=hijo;
				hash->operator [](heap[posicion]->dato)=posicion;
				hash->operator [](heap[hijo]->dato)=hijo;
				

	}//cambio con el hijo si corresponde
	else if(padre>0 && padre<= tope &&heap[posicion]->prioridad>heap[padre]->prioridad){
				NodoHeap<T>* aux = heap[posicion];
				int auxInt=heap[padre]->posicion;
				heap[posicion] = heap[padre];
				heap[padre]=aux;
				heap[padre]->posicion=auxInt;
				heap[posicion]->posicion = posicion;
				if(hijo<=tope){
					heap[hijo]->posicion=hijo;
					hash->operator [](heap[hijo]->dato)=hijo;
				}
				hash->operator [](heap[posicion]->dato)=posicion;
				hash->operator [](heap[padre]->dato)=padre;
				return heap[padre]->posicion;
				
	}
	return heap[posicion]->posicion;

}

template<class T>
int ColaHeapImp<T> :: cambiarPuntajeRecurso(int posicion, int cantidad){
	heap[posicion]->prioridad =heap[posicion]->prioridad + cantidad;
	return reorganizar(posicion);
}


template<class T>
void ColaHeapImp<T>::mostrarCola(){
	for(int i=1;i<tope+1;i++) {
		cout<<heap[i]->dato;
	}
}

template<class T>
int ColaHeapImp<T>::largo(){
	return tope;
}

template<class T>
ColaHeapImp<T> &ColaHeapImp<T>::operator=(const ColaHeapImp&c) {
	if(this != &c) {
		for(int i=1;i<tope+1;i++) {
			this->encolarConPrioridad(c.heap[i]->dato, c.heap[i]->prioridad);
		}
	}
	return *this;
}

//template<class T>
//int ColaHeapImp<T>::prioridadDelPrimero(){
//	return heap[1]->prioridad;
//}
template<class T>
T& ColaHeapImp<T>::devolverDato(T t)
{
	int pos=this->hash->operator [](t);
	return this->heap[pos]->dato;
}
template<class T>
T& ColaHeapImp<T>::DevolverMaximo()
{
	return this->heap[1]->dato;
}
template<class T>
bool ColaHeapImp<T>::EstaDefinido(T t)
{
	return this->hash->estaDefinido(t);
}

template<class T>
Puntero<Iterador<T>> ColaHeapImp<T>::ObtenerIterador() const
{
	lista->Vaciar();
	for(int i = 1; i < this->tope+1; i++){
			lista->AgregarPpio(heap[i]->dato);
	}
	Puntero<Iterador<T>> it=new IteradorListaImp<T>(lista);
	//delete lista;
	return it;
//Puntero<ListaImp<Puntero<Recurso>> lista=new ListaImp<Puntero<Recurso>>();
//Puntero<Iterador<T>> =this->hash->ObtenerIterador();
//return NULL;
}
#endif